{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Numerically Balanced Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #backtracking #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #回溯 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextBeautifulNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个更大的数值平衡数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果整数&nbsp; <code>x</code> 满足：对于每个数位&nbsp;<code>d</code> ，这个数位&nbsp;<strong>恰好</strong> 在 <code>x</code> 中出现 <code>d</code> 次。那么整数 <code>x</code> 就是一个 <strong>数值平衡数</strong> 。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，请你返回 <strong>严格大于</strong> <code>n</code> 的 <strong>最小数值平衡数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>\n",
    "22 是一个数值平衡数，因为：\n",
    "- 数字 2 出现 2 次 \n",
    "这也是严格大于 1 的最小数值平衡数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1000\n",
    "<strong>输出：</strong>1333\n",
    "<strong>解释：</strong>\n",
    "1333 是一个数值平衡数，因为：\n",
    "- 数字 1 出现 1 次。\n",
    "- 数字 3 出现 3 次。 \n",
    "这也是严格大于 1000 的最小数值平衡数。\n",
    "注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3000\n",
    "<strong>输出：</strong>3133\n",
    "<strong>解释：</strong>\n",
    "3133 是一个数值平衡数，因为：\n",
    "- 数字 1 出现 1 次。\n",
    "- 数字 3 出现 3 次。 \n",
    "这也是严格大于 3000 的最小数值平衡数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-numerically-balanced-number](https://leetcode.cn/problems/next-greater-numerically-balanced-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-numerically-balanced-number](https://leetcode.cn/problems/next-greater-numerically-balanced-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '1000', '3000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        _dic = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, \n",
    "14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322,\n",
    "41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, \n",
    "132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, \n",
    "221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, \n",
    "232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, \n",
    "244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, \n",
    "322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, \n",
    "331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, \n",
    "333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, \n",
    "444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        return _dic[bisect.bisect(_dic, n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        for i in range(n + 1, 2 ** 31):\n",
    "            cnt = Counter(str(i))\n",
    "            for k, v in cnt.items():\n",
    "                if int(k) != v:\n",
    "                    break\n",
    "            else:\n",
    "                return i \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        res = 1\n",
    "        while res:\n",
    "            n += 1\n",
    "            s = str(n)\n",
    "            cnt = Counter(s)\n",
    "            res = 0\n",
    "            for k, v in cnt.items():\n",
    "                if int(k) != v:\n",
    "                    res = 1\n",
    "                    break\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        for i in range(n+1,1000000000):\n",
    "            s=str(i)\n",
    "            cnt=Counter(s)\n",
    "            check=True\n",
    "            for c in s:\n",
    "                if cnt[c]!=int(c):\n",
    "                    check=False\n",
    "                    break\n",
    "            if check:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        # 判断是不是平衡数，应该是6的时间复杂度\n",
    "        def check(num: int) -> bool:\n",
    "            xf = collections.defaultdict(int)\n",
    "            for x in str(num):\n",
    "                xf[int(x)] += 1\n",
    "            for x, f in xf.items():\n",
    "                if x != f:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        x = n + 1\n",
    "        while check(x) == False:\n",
    "            x += 1\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return next(n for n in range(n + 1, 1234567) if all(int(x) == t for x, t in Counter(str(n)).items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        integer = n + 1\n",
    "        while 1:\n",
    "            if check(integer):\n",
    "                return integer \n",
    "            else:\n",
    "                integer += 1 \n",
    "\n",
    "def check(integer):\n",
    "    integer_str_counter = Counter(str(integer))\n",
    "    for item in integer_str_counter.items():\n",
    "        if int(item[0]) != item[1]:\n",
    "            return False \n",
    "    return True \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return next(n for n in range(n + 1, 1234567) if all(int(x) == t for x, t in Counter(str(n)).items()))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        # 13 14 15 24 1 2 3 4 5 6\n",
    "        res = [0, 1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        res.sort()\n",
    "        return res[bisect_left(res, n+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        #dic[num] == num\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        lst = [1,22,122,212,221,333,1333,3133,3313,3331,4444,14444,22333,23233,23323,23332,32233,32323,32332,33223,33232,33322,41444,44144,44414,44441,55555,122333,123233,123323,123332,132233,132323,132332,133223,133232,133322,155555,212333,213233,213323,213332,221333,223133,223313,223331,224444,231233,231323,231332,232133,232313,232331,233123,233132,233213,233231,233312,233321,242444,244244,244424,244442,312233,312323,312332,313223,313232,313322,321233,321323,321332,322133,322313,322331,323123,323132,323213,323231,323312,323321,331223,331232,331322,332123,332132,332213,332231,332312,332321,333122,333212,333221,422444,424244,424424,424442,442244,442424,442442,444224,444242,444422,515555,551555,555155,555515,555551,666666,1224444]\n",
    "        return lst[bisect.bisect(lst, n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        for i in range(n + 1, 1224445):\n",
    "            count = Counter(str(i))\n",
    "            if all(count[d] == int(d) for d in count):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        if n<1:\n",
    "            return 1\n",
    "        if n<10:\n",
    "            return 22\n",
    "        def count(n):\n",
    "            freq = {}\n",
    "            for i in str(n):\n",
    "                if int(i)>int(math.log10(n))+1:\n",
    "                    return False\n",
    "                freq[i] = freq.get(i, 0) + 1\n",
    "            for i in freq:\n",
    "                if freq[i]!= int(i):\n",
    "                   return False\n",
    "            return True\n",
    "        x = n + 1\n",
    "        while count(x) == False:\n",
    "            x += 1\n",
    "        return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def check(num):\n",
    "            num_str=str(num)\n",
    "            num_dict=defaultdict(int)\n",
    "            for i in range(len(num_str)):\n",
    "                num_dict[int(num_str[i])]+=1\n",
    "\n",
    "            for k ,v in num_dict.items():\n",
    "                if k!=v:\n",
    "                    return False\n",
    "            return True\n",
    "        x=n+1\n",
    "        while check(x)==False:\n",
    "            x+=1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            cnt = [0] * 10\n",
    "            tmp = n\n",
    "            while tmp:\n",
    "                cnt[tmp % 10] += 1\n",
    "                tmp //= 10             \n",
    "            if all(cnt[i] == i for i in range(10) if cnt[i]):\n",
    "                return n\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def check(num: int) -> bool:\n",
    "            xf = collections.defaultdict(int)\n",
    "            for x in str(num):\n",
    "                xf[int(x)] += 1\n",
    "            for x, f in xf.items():\n",
    "                if x != f:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        x = n + 1\n",
    "        while check(x) == False: \n",
    "            x += 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, n: int):\n",
    "        cnt = Counter(str(n))\n",
    "        for num, times in cnt.items():\n",
    "            if int(num) != times:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        res = n+1\n",
    "        while not self.check(res):\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def check(num: int) -> bool:\n",
    "            xf = collections.defaultdict(int)\n",
    "            for x in str(num):\n",
    "                xf[int(x)] += 1\n",
    "            for x, f in xf.items():\n",
    "                if x != f:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        x = n + 1\n",
    "        while check(x) == False:\n",
    "            x += 1\n",
    "        return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "balance = [\n",
    "    0, 1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444,\n",
    "    14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332,\n",
    "    33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555,\n",
    "    122333, 123233, 123323, 123332, 132233, 132323, 132332,\n",
    "    133223, 133232, 133322, 155555, 212333, 213233, 213323,\n",
    "    213332, 221333, 223133, 223313, 223331, 224444, 231233,\n",
    "    231323, 231332, 232133, 232313, 232331, 233123, 233132,\n",
    "    233213, 233231, 233312, 233321, 242444, 244244, 244424,\n",
    "    244442, 312233, 312323, 312332, 313223, 313232, 313322,\n",
    "    321233, 321323, 321332, 322133, 322313, 322331, 323123,\n",
    "    323132, 323213, 323231, 323312, 323321, 331223, 331232,\n",
    "    331322, 332123, 332132, 332213, 332231, 332312, 332321,\n",
    "    333122, 333212, 333221, 422444, 424244, 424424, 424442,\n",
    "    442244, 442424, 442442, 444224, 444242, 444422, 515555,\n",
    "    551555, 555155, 555515, 555551, 666666, 1224444\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return balance[bisect_right(balance, n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return next(n for n in range(n + 1, 1234567) if all(int(x) == t for x, t in Counter(str(n)).items()))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def check(num: int) -> bool:\n",
    "            num = str(num)\n",
    "            counter = {}\n",
    "            for i in num:\n",
    "                if not counter.get(i):\n",
    "                    counter[i] = 1\n",
    "                else:\n",
    "                    counter[i] += 1\n",
    "            for k,v in counter.items():\n",
    "                if int(k) != v:\n",
    "                    return False\n",
    "            return True\n",
    "        while True:\n",
    "            if check(n+1):\n",
    "                return n+1;\n",
    "            else:\n",
    "                n += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res = [1]\n",
    "num = 2\n",
    "while res[-1] <= 10**6:\n",
    "    s = str(num)\n",
    "    cnt = Counter(s)\n",
    "    if all(cnt[w] == int(w) for w in cnt):\n",
    "        res.append(num)\n",
    "    num += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return res[bisect.bisect_right(res, n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def check(n):\n",
    "            cnt = Counter(str(n))\n",
    "            for k, v in cnt.items():\n",
    "                if int(k) != v:\n",
    "                    return False \n",
    "            return True \n",
    "        ans = n + 1\n",
    "        while not check(ans):\n",
    "            ans += 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         avails = []\n",
    "#         for cnt in range(1,5):\n",
    "#             for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "#                 if sum(lst) >7:\n",
    "#                     continue \n",
    "#                 res = []\n",
    "#                 for num in lst:\n",
    "#                     res.extend([num] * num)\n",
    "#                 for r in permutations(res):\n",
    "#                     a = 0\n",
    "#                     for b in r:\n",
    "#                         a = a * 10 + b\n",
    "#                     avails.append(a)\n",
    "#         avails.sort()\n",
    "\n",
    "#         return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "from itertools import combinations, permutations\n",
    "\n",
    "nums = set()\n",
    "for cnt in range(1, 7):\n",
    "    for item in combinations(list(range(1, 8)), cnt):\n",
    "        if sum(item) <= 7:\n",
    "            lst = []\n",
    "            for num in item:\n",
    "                lst.extend([str(num)] * num)\n",
    "            for per in permutations(lst, len(lst)):\n",
    "                nums.add(int(\"\".join(per)))\n",
    "nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr = []\r\n",
    "def f(n):\r\n",
    "    d = {}\r\n",
    "    while n > 0:\r\n",
    "        d[n%10] = d.get(n%10,0) + 1\r\n",
    "        n //= 10\r\n",
    "    for k,v in d.items():\r\n",
    "        if k != v:\r\n",
    "            return False\r\n",
    "    return True\r\n",
    "for i in range(1,2**21):\r\n",
    "    if f(i):\r\n",
    "        arr.append(i)\r\n",
    "class Solution:\r\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\r\n",
    "        for a in arr:\r\n",
    "            if a > n:\r\n",
    "                return a\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        n += 1\n",
    "        while True:\n",
    "            c = Counter(str(n))\n",
    "            can = True\n",
    "            for k in c:\n",
    "                if int(k) != c[k]:\n",
    "                    can = False\n",
    "                    break\n",
    "            if can:                    \n",
    "                return n\n",
    "            n += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        \n",
    "        def check(num):\n",
    "            counter = Counter(str(num))\n",
    "            # print(counter)\n",
    "            for k in counter:\n",
    "                if int(k) != counter[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        i = n + 1\n",
    "        while check(i) is False:\n",
    "            i += 1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        balanced = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        balanced.sort()\n",
    "        for num in balanced:\n",
    "            if num > n:\n",
    "                return num\n",
    "        \n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        for i in range(n + 1, 6666667):\n",
    "            if all(int(k) == v for k, v in Counter(str(i)).items()):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations, permutations\n",
    "\n",
    "nums = set()\n",
    "for cnt in range(1, 7):\n",
    "    for item in combinations(list(range(1, 8)), cnt):\n",
    "        if sum(item) <= 7:\n",
    "            lst = []\n",
    "            for num in item:\n",
    "                lst.extend([str(num)] * num)\n",
    "            for per in permutations(lst, len(lst)):\n",
    "                nums.add(int(\"\".join(per)))\n",
    "nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return nums[bisect.bisect_right(nums, n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "\n",
    "        def check(num: int) -> bool:\n",
    "\n",
    "            xf = collections.defaultdict(int)\n",
    "\n",
    "            for x in str(num):\n",
    "\n",
    "                xf[int(x)] += 1\n",
    "\n",
    "            for x, f in xf.items():\n",
    "\n",
    "                if x != f:\n",
    "\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        \n",
    "\n",
    "        x = n + 1\n",
    "\n",
    "        while check(x) == False:\n",
    "\n",
    "            x += 1\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        tmp = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        idx = bisect_right(tmp, n)\n",
    "        return tmp[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        res = n + 1\n",
    "        while True:\n",
    "            cnt = [0] * 10 \n",
    "            t = res\n",
    "            while t:\n",
    "                cnt[t % 10] += 1\n",
    "                t //= 10 \n",
    "            ok = True\n",
    "            for i in range(10):\n",
    "                if cnt[i] != 0 and cnt[i] != i:\n",
    "                    ok = False\n",
    "                    break \n",
    "            if ok:\n",
    "                return res\n",
    "            res += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        path = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44224, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        \n",
    "        t = True\n",
    "        if n not in path:\n",
    "            t = False\n",
    "        path.append(n)\n",
    "        path = sorted(path)\n",
    "        if not t:\n",
    "            return path[path.index(n)+1]\n",
    "        else:\n",
    "            return path[path.index(n)+2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n):\n",
    "        def isBeautiful(n):\n",
    "            xf = collections.defaultdict(int)\n",
    "            for x in str(n):\n",
    "                xf[int(x)] += 1\n",
    "            for x, f in xf.items():\n",
    "                if x != f:\n",
    "                    return False\n",
    "            return True\n",
    "        if isBeautiful(n):\n",
    "            n += 1\n",
    "        while not isBeautiful(n):\n",
    "            n += 1\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def generate(base):\n",
    "            n = len(base)\n",
    "            res = []\n",
    "            now = 0\n",
    "            for index in range(n):\n",
    "                now = now * 10 + base[index]\n",
    "            res.append(now)\n",
    "\n",
    "            while True:\n",
    "                p = None\n",
    "                for index in range(n - 2, -1, -1):\n",
    "                    if base[index] < base[index + 1]:\n",
    "                        p = index\n",
    "                        break\n",
    "                if p is None:\n",
    "                    break\n",
    "                \n",
    "                q = n - 1\n",
    "                for index in range(p + 1, n):\n",
    "                    if base[index] <= base[p]:\n",
    "                        q = index - 1\n",
    "                        break\n",
    "                \n",
    "                base[p], base[q] = base[q], base[p]\n",
    "                l = p + 1\n",
    "                r = n - 1\n",
    "                while l < r:\n",
    "                    base[l], base[r] = base[r], base[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                \n",
    "                now = 0\n",
    "                for index in range(n):\n",
    "                    now = now * 10 + base[index]\n",
    "                res.append(now)\n",
    "\n",
    "            \n",
    "            return res\n",
    "        num_list = [1, 22, 333, 4444, 55555, 666666, 1224444]\n",
    "        num_list.extend(generate([1, 2, 2]))\n",
    "        num_list.extend(generate([1, 3, 3, 3]))\n",
    "        num_list.extend(generate([1, 4, 4, 4, 4]))\n",
    "        num_list.extend(generate([1, 5, 5, 5, 5, 5]))\n",
    "        num_list.extend(generate([1, 2, 2, 3, 3, 3]))\n",
    "        num_list.extend(generate([2, 2, 3, 3, 3]))\n",
    "        num_list.extend(generate([2, 2, 4, 4, 4, 4]))\n",
    "        for num in sorted(num_list):\n",
    "            if n < num:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def backtracking(cnt):\n",
    "            if(cnt == len(nums)):\n",
    "                self.result.append(int(''.join(self.path)))\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if(book[i] == 1):\n",
    "                    continue\n",
    "                if(i>0 and nums[i-1]==nums[i] and book[i-1]==0):\n",
    "                    continue\n",
    "                book[i] = 1\n",
    "                self.path.append(nums[i])\n",
    "                backtracking(cnt+1)\n",
    "                book[i] = 0\n",
    "                self.path.pop()\n",
    "            return\n",
    "        mapping = {\n",
    "            1:([['1']],22)\n",
    "            ,2:([['2','2']],122)\n",
    "            ,3:([['1','2','2'], ['3','3','3']],1333)\n",
    "            ,4:([['1','3','3','3'], ['4','4','4','4']],14444)\n",
    "            ,5:([['2','2','3','3','3'],['1','4','4','4','4'],['5','5','5','5','5']],122333)\n",
    "            ,6:([['1','5','5','5','5','5'],['1','2','2','3','3','3'],['2','2','4','4','4','4'],['6','6','6','6','6','6']],1224444)\n",
    "        }\n",
    "        ncnt = len(str(n))\n",
    "        if(ncnt == 7):\n",
    "            return 1224444\n",
    "        path = []\n",
    "        for nums in mapping[ncnt][0]:\n",
    "            self.path = []\n",
    "            self.result = []\n",
    "            book = [0]*len(nums)\n",
    "            backtracking(0)\n",
    "            path += self.result[:]\n",
    "        path.sort()\n",
    "        for num in path:\n",
    "            if(num > n):\n",
    "                return num \n",
    "        return mapping[ncnt][1]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        pro_lst = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        for num in pro_lst:\n",
    "           if num > n:\n",
    "               return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        lst = [1,22,122,212,221,333,1333,3133,3313,3331,4444,14444,22333,23233,23323,23332,32233,32323,32332,33223,33232,33322,41444,44144,44414,44441,55555,122333,123233,123323,123332,132233,132323,132332,133223,133232,133322,155555,212333,213233,213323,213332,221333,223133,223313,223331,224444,231233,231323,231332,232133,232313,232331,233123,233132,233213,233231,233312,233321,242444,244244,244424,244442,312233,312323,312332,313223,313232,313322,321233,321323,321332,322133,322313,322331,323123,323132,323213,323231,323312,323321,331223,331232,331322,332123,332132,332213,332231,332312,332321,333122,333212,333221,422444,424244,424424,424442,442244,442424,442442,444224,444242,444422,515555,551555,555155,555515,555551,666666,1224444]\n",
    "        return lst[bisect.bisect(lst, n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        balanced = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "\n",
    "        return balanced[bisect.bisect_right(balanced,n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def backtracking(cnt):\n",
    "            if(cnt == len(nums)):\n",
    "                self.result.append(int(''.join(self.path)))\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if(book[i] == 1):\n",
    "                    continue\n",
    "                if(i>0 and nums[i-1]==nums[i] and book[i-1]==0):\n",
    "                    continue\n",
    "                book[i] = 1\n",
    "                self.path.append(nums[i])\n",
    "                backtracking(cnt+1)\n",
    "                book[i] = 0\n",
    "                self.path.pop()\n",
    "            return\n",
    "        mapping = {\n",
    "            1:([['1']],22)\n",
    "            ,2:([['2','2']],122)\n",
    "            ,3:([['1','2','2'], ['3','3','3']],1333)\n",
    "            ,4:([['1','3','3','3'], ['4','4','4','4']],14444)\n",
    "            ,5:([['2','2','3','3','3'],['1','4','4','4','4'],['5','5','5','5','5']],122333)\n",
    "            ,6:([['1','5','5','5','5','5'],['1','2','2','3','3','3'],['2','2','4','4','4','4'],['6','6','6','6','6','6']],1224444)\n",
    "        }\n",
    "        ncnt = len(str(n))\n",
    "        if(ncnt == 7):\n",
    "            return 1224444\n",
    "        path = []\n",
    "        for nums in mapping[ncnt][0]:\n",
    "            self.path = []\n",
    "            self.result = []\n",
    "            book = [0]*len(nums)\n",
    "            backtracking(0)\n",
    "            path += self.result[:]\n",
    "        path.sort()\n",
    "        for num in path:\n",
    "            if(num > n):\n",
    "                return num \n",
    "        return mapping[ncnt][1]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "\n",
    "        while True:\n",
    "\n",
    "            n += 1\n",
    "\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "\n",
    "                return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        r = 1666666\n",
    "        l = n+1\n",
    "        def check(num)->bool:\n",
    "            c = Counter(str(num))\n",
    "            for key,value in c.items():\n",
    "                if c[key]!=int(key):\n",
    "                    return False\n",
    "            return True\n",
    "        while l<r+1:\n",
    "            if check(l):\n",
    "                return l\n",
    "            else:\n",
    "                l+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations, permutations\n",
    "\n",
    "nums = set()\n",
    "for cnt in range(1, 7):\n",
    "    for item in combinations(list(range(1, 8)), cnt):\n",
    "        if sum(item) <= 7:\n",
    "            lst = []\n",
    "            for num in item:\n",
    "                lst.extend([str(num)] * num)\n",
    "            for per in permutations(lst, len(lst)):\n",
    "                nums.add(int(\"\".join(per)))\n",
    "nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 枚举+排列组合+二分查找\n",
    "from itertools import combinations, permutations\n",
    "\n",
    "nums = set()\n",
    "for cnt in range(1, 7):\n",
    "    for item in combinations(list(range(1, 7)), cnt):\n",
    "        if sum(item) <= 7:\n",
    "            lst = []\n",
    "            for num in item:\n",
    "                lst.extend([str(num)] * num)\n",
    "\n",
    "            for per in permutations(lst, len(lst)):\n",
    "                nums.add(int(\"\".join(per)))\n",
    "\n",
    "nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "\n",
    "\n",
    "# 模拟\n",
    "class Solution2:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        res = [1,22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]\n",
    "        return res[bisect_left(res, n + 1)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 枚举+排列组合+二分查找\n",
    "from itertools import combinations, permutations\n",
    "\n",
    "nums = set()\n",
    "for cnt in range(1, 7):\n",
    "    for item in combinations(list(range(1, 7)), cnt):\n",
    "        if sum(item) <= 7:\n",
    "            lst = []\n",
    "            for num in item:\n",
    "                lst.extend([str(num)] * num)\n",
    "\n",
    "            for per in permutations(lst, len(lst)):\n",
    "                nums.add(int(\"\".join(per)))\n",
    "\n",
    "nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "\n",
    "\n",
    "# 模拟\n",
    "class Solution2:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "      if n == 0:  return 1\n",
    "      if n < 22:  return 22\n",
    "      numDict = {3: [[1, 2], [3]], 4: [[1, 3], [4]], 5: [[1, 4], [2, 3], [5]], 6: [[1, 2, 3], [1, 5], [2, 4], [6]], 7: [[1, 2, 4], [1, 6], [2, 5], [3, 4], [7]]}\n",
    "      \n",
    "      maxLen = len(str(n))\n",
    "      if n >= int(str(maxLen) * maxLen):\n",
    "        n = 10 ** maxLen\n",
    "        maxLen += 1\n",
    "      nums = []\n",
    "      def build(numDict, pre):\n",
    "        if pre > 10 ** (maxLen-1):\n",
    "          nums.append(pre)\n",
    "          return\n",
    "        \n",
    "        for i in numDict.keys():\n",
    "          if numDict[i]:\n",
    "            pre = pre * 10 + i\n",
    "            numDict[i] -= 1\n",
    "            build(numDict, pre)\n",
    "            pre = (pre - i) // 10\n",
    "            numDict[i] += 1\n",
    "      \n",
    "      for i in numDict[maxLen]:\n",
    "        cur = dict()\n",
    "        for j in i: cur[j] = j\n",
    "        build(cur, 0)\n",
    "      nums.sort()\n",
    "      L, R = 0, len(nums)-1\n",
    "      while L <= R:\n",
    "        mid = (L + R) // 2\n",
    "        if n >= nums[mid]: L = mid + 1\n",
    "        else: R = mid - 1\n",
    "      return nums[L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        while True:\n",
    "            n += 1\n",
    "            if all(int(k) == v for k, v in Counter(str(n)).items()):\n",
    "                return n\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "ss = SortedSet([1, 22, 333, 4444, 55555, 666666, 7777777])\n",
    "for x in itertools.permutations(\"122\", 3):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1333\", 4):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"22333\", 5):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"14444\", 5):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"122333\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"155555\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"224444\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1224444\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"3334444\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1666666\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"2255555\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return ss[ss.bisect_right(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "      if n == 0:  return 1\n",
    "      if n < 22:  return 22\n",
    "      numDict = {3: [[1, 2], [3]], 4: [[1, 3], [4]], 5: [[1, 4], [2, 3], [5]], 6: [[1, 2, 3], [1, 5], [2, 4], [6]], 7: [[1, 2, 4], [1, 6], [2, 5], [3, 4], [7]]}\n",
    "      \n",
    "      maxLen = len(str(n))\n",
    "      if n >= int(str(maxLen) * maxLen):\n",
    "        n = 10 ** maxLen\n",
    "        maxLen += 1\n",
    "      nums = []\n",
    "      def build(numDict, pre):\n",
    "        if pre > 10 ** (maxLen-1):\n",
    "          nums.append(pre)\n",
    "          return\n",
    "        \n",
    "        for i in numDict.keys():\n",
    "          if numDict[i]:\n",
    "            pre = pre * 10 + i\n",
    "            numDict[i] -= 1\n",
    "            build(numDict, pre)\n",
    "            pre = (pre - i) // 10\n",
    "            numDict[i] += 1\n",
    "      \n",
    "      for i in numDict[maxLen]:\n",
    "        cur = dict()\n",
    "        for j in i: cur[j] = j\n",
    "        build(cur, 0)\n",
    "      nums.sort()\n",
    "      L, R = 0, len(nums)-1\n",
    "      while L <= R:\n",
    "        mid = (L + R) // 2\n",
    "        if n >= nums[mid]: L = mid + 1\n",
    "        else: R = mid - 1\n",
    "      return nums[L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        def backtracking(cnt):\n",
    "            if(cnt == len(nums)):\n",
    "                self.result.append(int(''.join(self.path)))\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if(book[i] == 1):\n",
    "                    continue\n",
    "                if(i>0 and nums[i-1]==nums[i] and book[i-1]==0):\n",
    "                    continue\n",
    "                book[i] = 1\n",
    "                self.path.append(nums[i])\n",
    "                backtracking(cnt+1)\n",
    "                book[i] = 0\n",
    "                self.path.pop()\n",
    "            return\n",
    "        mapping = {\n",
    "            1:([['1']],22)\n",
    "            ,2:([['2','2']],122)\n",
    "            ,3:([['1','2','2'], ['3','3','3']],1333)\n",
    "            ,4:([['1','3','3','3'], ['4','4','4','4']],14444)\n",
    "            ,5:([['2','2','3','3','3'],['1','4','4','4','4'],['5','5','5','5','5']],122333)\n",
    "            ,6:([['1','5','5','5','5','5'],['1','2','2','3','3','3'],['2','2','4','4','4','4'],['6','6','6','6','6','6']],1224444)\n",
    "        }\n",
    "        ncnt = len(str(n))\n",
    "        if(ncnt == 7):\n",
    "            return 1224444\n",
    "        path = []\n",
    "        for nums in mapping[ncnt][0]:\n",
    "            self.path = []\n",
    "            self.result = []\n",
    "            book = [0]*len(nums)\n",
    "            backtracking(0)\n",
    "            path += self.result[:]\n",
    "        path.sort()\n",
    "        for num in path:\n",
    "            if(num > n):\n",
    "                return num \n",
    "        return mapping[ncnt][1]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "ss = SortedSet([1, 22, 333, 4444, 55555, 666666, 7777777])\n",
    "for x in itertools.permutations(\"122\", 3):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1333\", 4):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"22333\", 5):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"14444\", 5):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"122333\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"155555\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"224444\", 6):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1224444\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"3334444\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"1666666\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "for x in itertools.permutations(\"2255555\", 7):\n",
    "    ss.add(int(\"\".join(x)))\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        return ss[ss.bisect_right(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        count = len(str(n))\n",
    "        avails = []\n",
    "        combs = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "        for lst in combs:\n",
    "            avails.extend(self.get_combine_numbers(lst))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "\n",
    "    def dfs(self, cur, count, nxt):\n",
    "        ret = []\n",
    "        for i in range(nxt, count-cur+1):\n",
    "            if cur + i == count:\n",
    "                ret.append([i])\n",
    "            else:\n",
    "                ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "        return ret\n",
    "\n",
    "    def get_combine_numbers(self, combine):\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                ans.append(int(''.join(str(i) for i in nums)))\n",
    "                return\n",
    "\n",
    "            for i in range(idx, n):\n",
    "                if i > idx and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                helper(idx + 1)\n",
    "                nums[idx], nums[i] = nums[i], nums[idx]\n",
    "\n",
    "        nums = []\n",
    "        for i in combine:\n",
    "            nums.extend([i] * i)\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = []\n",
    "        helper(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        count = len(str(n))\n",
    "        avails = []\n",
    "        combs = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "        for lst in combs:\n",
    "            # res = []\n",
    "            # for num in lst:\n",
    "            #     res.extend([num]*num)\n",
    "            \n",
    "            for r in self.get_combine_numbers(lst):\n",
    "                # a = 0\n",
    "                # for b in r:\n",
    "                #     a = a * 10 + b\n",
    "                avails.append(r)\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "\n",
    "    def dfs(self, cur, count, nxt):\n",
    "        ret = []\n",
    "        for i in range(nxt, count + 1):\n",
    "            if cur + i > count:\n",
    "                return ret\n",
    "            elif cur + i == count:\n",
    "                ret.append([i])\n",
    "            else:\n",
    "                ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "        return ret\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         count = len(str(n))\n",
    "#         numbers = []\n",
    "#         combines = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "#         for combine in combines:\n",
    "#             numbers.extend(self.get_combine_numbers(combine))\n",
    "#         numbers.sort()\n",
    "#         idx = bisect.bisect_right(numbers, n)\n",
    "#         return numbers[idx]\n",
    "\n",
    "    def get_combine_numbers(self, combine):\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                ans.append(int(''.join(str(i) for i in nums)))\n",
    "                return\n",
    "\n",
    "            used = set()\n",
    "            for i in range(idx, n):\n",
    "                if nums[i] not in used:\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    helper(idx + 1)\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    used.add(nums[i])\n",
    "\n",
    "        nums = []\n",
    "        for i in combine:\n",
    "            nums.extend([i] * i)\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = []\n",
    "        helper(0)\n",
    "        return ans\n",
    "\n",
    "#     def dfs(self, cur, count, nxt):\n",
    "#         ret = []\n",
    "#         for i in range(nxt, count + 1):\n",
    "#             if cur + i > count:\n",
    "#                 return ret\n",
    "#             elif cur + i == count:\n",
    "#                 ret.append([i])\n",
    "#             else:\n",
    "#                 ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "#         return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "      if n == 0:  return 1\n",
    "      if n < 22:  return 22\n",
    "      numDict = {3: [[1, 2], [3]], 4: [[1, 3], [4]], 5: [[1, 4], [2, 3], [5]], 6: [[1, 2, 3], [1, 5], [2, 4], [6]], 7: [[1, 2, 4], [1, 6], [2, 5], [3, 4], [7]]}\n",
    "      \n",
    "      maxLen = len(str(n))\n",
    "      if n >= int(str(maxLen) * maxLen):\n",
    "        n = 10 ** maxLen\n",
    "        maxLen += 1\n",
    "      nums = []\n",
    "      def build(numDict, pre):\n",
    "        if pre > 10 ** (maxLen-1):\n",
    "          nums.append(pre)\n",
    "          return\n",
    "        \n",
    "        for i in numDict.keys():\n",
    "          if numDict[i]:\n",
    "            pre = pre * 10 + i\n",
    "            numDict[i] -= 1\n",
    "            build(numDict, pre)\n",
    "            pre = (pre - i) // 10\n",
    "            numDict[i] += 1\n",
    "      \n",
    "      for i in numDict[maxLen]:\n",
    "        cur = dict()\n",
    "        for j in i: cur[j] = j\n",
    "        build(cur, 0)\n",
    "      nums.sort()\n",
    "      L, R = 0, len(nums)-1\n",
    "      while L <= R:\n",
    "        mid = (L + R) // 2\n",
    "        if n >= nums[mid]: L = mid + 1\n",
    "        else: R = mid - 1\n",
    "      return nums[L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "      if n == 0:  return 1\n",
    "      if n < 22:  return 22\n",
    "      numDict = {3: [[1, 2], [3]], 4: [[1, 3], [4]], 5: [[1, 4], [2, 3], [5]], 6: [[1, 2, 3], [1, 5], [2, 4], [6]], 7: [[1, 2, 4], [1, 6], [2, 5], [3, 4], [7]]}\n",
    "      \n",
    "      maxLen = len(str(n))\n",
    "      if n >= int(str(maxLen) * maxLen):\n",
    "        n = 10 ** maxLen\n",
    "        maxLen += 1\n",
    "      nums = []\n",
    "      def build(numDict, pre):\n",
    "        if pre > 10 ** (maxLen-1):\n",
    "          nums.append(pre)\n",
    "          return\n",
    "        \n",
    "        for i in numDict.keys():\n",
    "          if numDict[i]:\n",
    "            pre = pre * 10 + i\n",
    "            numDict[i] -= 1\n",
    "            build(numDict, pre)\n",
    "            pre = (pre - i) // 10\n",
    "            numDict[i] += 1\n",
    "      \n",
    "      for i in numDict[maxLen]:\n",
    "        cur = dict()\n",
    "        for j in i: cur[j] = j\n",
    "        build(cur, 0)\n",
    "      nums.sort()\n",
    "      L, R = 0, len(nums)-1\n",
    "      while L <= R:\n",
    "        mid = (L + R) // 2\n",
    "        if n >= nums[mid]: L = mid + 1\n",
    "        else: R = mid - 1\n",
    "      return nums[L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        count = len(str(n))\n",
    "        avails = []\n",
    "        combs = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "        for lst in combs:\n",
    "            avails.extend(self.get_combine_numbers(lst))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "\n",
    "    def dfs(self, cur, count, nxt):\n",
    "        ret = []\n",
    "        for i in range(nxt, count-cur+1):\n",
    "            if cur + i == count:\n",
    "                ret.append([i])\n",
    "            else:\n",
    "                ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "        return ret\n",
    "\n",
    "    def get_combine_numbers(self, combine):\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                ans.append(int(''.join(str(i) for i in nums)))\n",
    "                return\n",
    "\n",
    "            used = set()\n",
    "            for i in range(idx, n):\n",
    "                if nums[i] not in used:\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    helper(idx + 1)\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    used.add(nums[i])\n",
    "\n",
    "        nums = []\n",
    "        for i in combine:\n",
    "            nums.extend([i] * i)\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = []\n",
    "        helper(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        count = len(str(n))\n",
    "        avails = []\n",
    "        combs = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "        for lst in combs:\n",
    "            avails.extend(self.get_combine_numbers(lst))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "\n",
    "    def dfs(self, cur, count, nxt):\n",
    "        ret = []\n",
    "        for i in range(nxt, count-cur+1):\n",
    "            if cur + i == count:\n",
    "                ret.append([i])\n",
    "            else:\n",
    "                ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "        return ret\n",
    "\n",
    "    def get_combine_numbers(self, combine):\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                ans.append(int(''.join(str(i) for i in nums)))\n",
    "                return\n",
    "\n",
    "            for i in range(idx, n):\n",
    "                if i > idx and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                helper(idx + 1)\n",
    "                nums[idx], nums[i] = nums[i], nums[idx]\n",
    "\n",
    "        nums = []\n",
    "        for i in combine:\n",
    "            nums.extend([i] * i)\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = []\n",
    "        helper(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         count = len(str(n))\n",
    "#         avails = []\n",
    "#         combs = set(self.dfs(0, count, 1) + self.dfs(0, count + 1, 1))\n",
    "#         for lst in combs:\n",
    "#             res = []\n",
    "#             for num in lst:\n",
    "#                 res.extend([num]*num)\n",
    "            \n",
    "#             for r in permutations(res):\n",
    "#                 a = 0\n",
    "#                 for b in r:\n",
    "#                     a = a * 10 + b\n",
    "#                 avails.append(a)\n",
    "#         avails.sort()\n",
    "\n",
    "#         return avails[bisect.bisect(avails, n)]\n",
    "\n",
    "#     def dfs(self, cur, count, nxt):\n",
    "#         ret = []\n",
    "#         for i in range(nxt, count + 1):\n",
    "#             if cur + i > count:\n",
    "#                 return ret\n",
    "#             elif cur + i == count:\n",
    "#                 ret.append((i,))\n",
    "#             else:\n",
    "#                 ret.extend([tuple([i] + list(j)) for j in self.dfs(cur + i, count, i + 1)])\n",
    "#         return ret\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        count = len(str(n))\n",
    "        numbers = []\n",
    "        combines = self.dfs(0, count, 1) + self.dfs(0, count + 1, 1)\n",
    "        for combine in combines:\n",
    "            numbers.extend(self.get_combine_numbers(combine))\n",
    "        numbers.sort()\n",
    "        idx = bisect.bisect_right(numbers, n)\n",
    "        return numbers[idx]\n",
    "\n",
    "    def get_combine_numbers(self, combine):\n",
    "        def helper(idx):\n",
    "            if idx == n - 1:\n",
    "                ans.append(int(''.join(str(i) for i in nums)))\n",
    "                return\n",
    "\n",
    "            used = set()\n",
    "            for i in range(idx, n):\n",
    "                if nums[i] not in used:\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    helper(idx + 1)\n",
    "                    nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                    used.add(nums[i])\n",
    "\n",
    "        nums = []\n",
    "        for i in combine:\n",
    "            nums.extend([i] * i)\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = []\n",
    "        helper(0)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, cur, count, nxt):\n",
    "        ret = []\n",
    "        for i in range(nxt, count + 1):\n",
    "            if cur + i > count:\n",
    "                return ret\n",
    "            elif cur + i == count:\n",
    "                ret.append([i])\n",
    "            else:\n",
    "                ret.extend([[i] + j for j in self.dfs(cur + i, count, i + 1)])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    break \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    # a = 0\n",
    "                    # for b in r:\n",
    "                    #     a = a * 10 + b\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "avails = []\n",
    "for cnt in range(1,5):\n",
    "    for lst in combinations(list(range(1,8)), cnt):\n",
    "        if sum(lst) >7:\n",
    "            continue \n",
    "        res = []\n",
    "        for num in lst:\n",
    "            res.extend([str(num)] * num)\n",
    "        for r in permutations(res):\n",
    "            # a = 0\n",
    "            # for b in r:\n",
    "            #     a = a * 10 + b\n",
    "            avails.append(int(\"\".join(r)))\n",
    "avails.sort()\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    break \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    # a = 0\n",
    "                    # for b in r:\n",
    "                    #     a = a * 10 + b\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "avails = []\n",
    "for cnt in range(1,5):\n",
    "    for lst in combinations(list(range(1,8)), cnt):\n",
    "        if sum(lst) >7:\n",
    "            continue \n",
    "        res = []\n",
    "        for num in lst:\n",
    "            res.extend([str(num)] * num)\n",
    "        for r in permutations(res):\n",
    "            # a = 0\n",
    "            # for b in r:\n",
    "            #     a = a * 10 + b\n",
    "            avails.append(int(\"\".join(r)))\n",
    "avails.sort()\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    continue \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([num] * num)\n",
    "                for r in permutations(res):\n",
    "                    a = 0\n",
    "                    for b in r:\n",
    "                        a = a * 10 + b\n",
    "                    avails.append(a)\n",
    "        avails.sort()\n",
    "        \n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    continue \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([num] * num)\n",
    "                for r in permutations(res):\n",
    "                    a = 0\n",
    "                    for b in r:\n",
    "                        a = a * 10 + b\n",
    "                    avails.append(a)\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    continue \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    # a = 0\n",
    "                    # for b in r:\n",
    "                    #     a = a * 10 + b\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1, 5):\n",
    "            for lst in combinations(list(range(1, 8)), cnt):\n",
    "                if sum(lst) > 7:\n",
    "                    continue\n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "avails = []\n",
    "for cnt in range(1,5):\n",
    "    for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "        if sum(lst) >7:\n",
    "            continue \n",
    "        res = []\n",
    "        for num in lst:\n",
    "            res.extend([str(num)] * num)\n",
    "        for r in permutations(res):\n",
    "            # a = 0\n",
    "            # for b in r:\n",
    "            #     a = a * 10 + b\n",
    "            avails.append(int(\"\".join(r)))\n",
    "avails.sort()\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1,5):\n",
    "            for lst in combinations(list(range(1,9-cnt)), cnt):\n",
    "                if sum(lst) >7:\n",
    "                    continue \n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    # a = 0\n",
    "                    # for b in r:\n",
    "                    #     a = a * 10 + b\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "                \n",
    "# from itertools import combinations, permutations\n",
    "\n",
    "# nums = set()\n",
    "# for cnt in range(1, 7):\n",
    "#     for item in combinations(list(range(1, 8)), cnt):\n",
    "#         if sum(item) <= 7:\n",
    "#             lst = []\n",
    "#             for num in item:\n",
    "#                 lst.extend([str(num)] * num)\n",
    "#             for per in permutations(lst, len(lst)):\n",
    "#                 nums.add(int(\"\".join(per)))\n",
    "# nums = sorted(list(nums))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nextBeautifulNumber(self, n: int) -> int:\n",
    "#         return nums[bisect.bisect_right(nums, n)]\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextBeautifulNumber(self, n: int) -> int:\n",
    "        avails = []\n",
    "        for cnt in range(1, 5):\n",
    "            for lst in combinations(list(range(1, 8)), cnt):\n",
    "                if sum(lst) > 7:\n",
    "                    continue\n",
    "                res = []\n",
    "                for num in lst:\n",
    "                    res.extend([str(num)] * num)\n",
    "                for r in permutations(res):\n",
    "                    avails.append(int(\"\".join(r)))\n",
    "        avails.sort()\n",
    "        return avails[bisect.bisect(avails, n)]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
